package leetcode.simple._101;

import structure.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author mgl
 * @version 1.0
 * @description 101题，判断树是否对称
 * @date 2023/7/8 23:29
 */
public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        return subSymmetric(root.left,root.right);
    }

    boolean subSymmetric(TreeNode left,TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return subSymmetric(left.right,right.left) && subSymmetric(left.left,right.right);
    }
    public boolean isSymmetric_old(TreeNode root) {
        //if ((root.left == null && root.right != null) || (root.left != null && root.right == null)) return false;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int index = 0;
            int[] arr = new int[i];
            TreeNode pop = queue.poll();
            if (pop.left == null || pop.left.val == 500) {
                arr[index++] = 500;
                queue.add(new TreeNode(500));
            } else {
                arr[index++] = pop.val;
                queue.add(pop.left);
            }

            if (pop.right == null || pop.right.val == 500) {
                arr[index++] = 500;
                queue.add(new TreeNode(500));
            } else {
                arr[index++] = pop.val;
                queue.add(pop.left);
            }

            boolean temp = true;
            for (int j = 0; j < i / 2; j++) {
                if (arr[j] != 500) temp = false;
                if (arr[j] != arr[i - j - 1]) return false;
            }

            if (temp) return true;
            i *= 2;
        }

        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(2);
        left.left = new TreeNode(3);
        left.right = new TreeNode(4);
        right.left = new TreeNode(4);
        right.right = new TreeNode(3);
        root.left = left;
        root.right = right;
        new SymmetricTree().isSymmetric(root);
    }
}
